var _START_TO_START = 0,
  _START_TO_END = 1,
  _END_TO_END = 2,
  _END_TO_START = 3,
  _BOOKMARK_ID = 0;

function _updateCollapsed(range) {
  range.collapsed =
    range.startContainer === range.endContainer &&
    range.startOffset === range.endOffset;
  return range;
}
/**
	cloneContents: _copyAndDelete(this, true, false)
	extractContents: _copyAndDelete(this, true, true)
	deleteContents: _copyAndDelete(this, false, true)
*/
function _copyAndDelete(range, isCopy, isDelete) {
  var doc = range.doc,
    nodeList = [];
  //split a textNode
  function splitTextNode(node, startOffset, endOffset) {
    var length = node.nodeValue.length,
      centerNode;
    if (isCopy) {
      var cloneNode = node.cloneNode(true);
      if (startOffset > 0) {
        centerNode = cloneNode.splitText(startOffset);
      } else {
        centerNode = cloneNode;
      }
      if (endOffset < length) {
        centerNode.splitText(endOffset - startOffset);
      }
    }
    if (isDelete) {
      var center = node;
      if (startOffset > 0) {
        center = node.splitText(startOffset);
        range.setStart(node, startOffset);
      }
      if (endOffset < length) {
        var right = center.splitText(endOffset - startOffset);
        range.setEnd(right, 0);
      }
      nodeList.push(center);
    }
    return centerNode;
  }
  function removeNodes() {
    if (isDelete) {
      range.up().collapse(true);
    }
    for (var i = 0, len = nodeList.length; i < len; i++) {
      var node = nodeList[i];
      if (node.parentNode) {
        node.parentNode.removeChild(node);
      }
    }
  }

  var copyRange = range.cloneRange().down();

  var start = -1,
    incStart = -1,
    incEnd = -1,
    end = -1,
    ancestor = range.commonAncestor(),
    frag = doc.createDocumentFragment();
  // startContainer is textNode and startContainer == endContainer
  if (ancestor.nodeType == 3) {
    var textNode = splitTextNode(ancestor, range.startOffset, range.endOffset);
    if (isCopy) {
      frag.appendChild(textNode);
    }
    removeNodes();
    return isCopy ? frag : range;
  }
  // other case
  function extractNodes(parent, frag) {
    var node = parent.firstChild,
      nextNode;
    while (node) {
      var testRange = new KRange(doc).selectNode(node);
      start = testRange.compareBoundaryPoints(_START_TO_END, range);
      if (start >= 0 && incStart <= 0) {
        incStart = testRange.compareBoundaryPoints(_START_TO_START, range);
      }
      if (incStart >= 0 && incEnd <= 0) {
        incEnd = testRange.compareBoundaryPoints(_END_TO_END, range);
      }
      if (incEnd >= 0 && end <= 0) {
        end = testRange.compareBoundaryPoints(_END_TO_START, range);
      }
      if (end >= 0) {
        return false;
      }
      nextNode = node.nextSibling;
      if (start > 0) {
        if (node.nodeType == 1) {
          if (incStart >= 0 && incEnd <= 0) {
            if (isCopy) {
              frag.appendChild(node.cloneNode(true));
            }
            if (isDelete) {
              nodeList.push(node);
            }
          } else {
            var childFlag;
            if (isCopy) {
              childFlag = node.cloneNode(false);
              frag.appendChild(childFlag);
            }
            if (extractNodes(node, childFlag) === false) {
              return false;
            }
          }
        } else if (node.nodeType == 3) {
          var textNode;
          if (node == copyRange.startContainer) {
            textNode = splitTextNode(
              node,
              copyRange.startOffset,
              node.nodeValue.length
            );
          } else if (node == copyRange.endContainer) {
            textNode = splitTextNode(node, 0, copyRange.endOffset);
          } else {
            textNode = splitTextNode(node, 0, node.nodeValue.length);
          }
          if (isCopy) {
            // TODO: IE9有时候报错
            try {
              frag.appendChild(textNode);
            } catch (e) {}
          }
        }
      }
      node = nextNode;
    }
  }

  extractNodes(ancestor, frag);

  if (isDelete) {
    range.up().collapse(true);
  }
  for (var i = 0, len = nodeList.length; i < len; i++) {
    var node = nodeList[i];
    if (node.parentNode) {
      node.parentNode.removeChild(node);
    }
  }
  return isCopy ? frag : range;
}
//在marquee、select元素里不能使用moveToElementText，IE专用
function _moveToElementText(range, el) {
  var node = el;
  while (node) {
    var knode = K(node);
    if (knode.name == "marquee" || knode.name == "select") {
      return;
    }
    node = node.parentNode;
  }
  // IE有时候报错，屏蔽错误
  try {
    range.moveToElementText(el);
  } catch (e) {}
}
//根据原生Range，取得开始节点和结束节点的位置。IE专用
function _getStartEnd(rng, isStart) {
  var doc = rng.parentElement().ownerDocument,
    pointRange = rng.duplicate();
  pointRange.collapse(isStart);
  var parent = pointRange.parentElement(),
    nodes = parent.childNodes;
  if (nodes.length === 0) {
    return { node: parent.parentNode, offset: K(parent).index() };
  }
  var startNode = doc,
    startPos = 0,
    cmp = -1;
  var testRange = rng.duplicate();
  _moveToElementText(testRange, parent);
  for (var i = 0, len = nodes.length; i < len; i++) {
    var node = nodes[i];
    cmp = testRange.compareEndPoints("StartToStart", pointRange);
    if (cmp === 0) {
      return { node: node.parentNode, offset: i };
    }
    if (node.nodeType == 1) {
      var nodeRange = rng.duplicate(),
        dummy,
        knode = K(node),
        newNode = node;
      // <table></table><img>ab[cd]ef
      if (knode.isControl()) {
        dummy = doc.createElement("span");
        knode.after(dummy);
        newNode = dummy;
        // 0123456[7]89<table><tr><td>123</td></tr></table>
        startPos += knode.text().replace(/\r\n|\n|\r/g, "").length;
      }
      _moveToElementText(nodeRange, newNode);
      testRange.setEndPoint("StartToEnd", nodeRange);
      if (cmp > 0) {
        startPos += nodeRange.text.replace(/\r\n|\n|\r/g, "").length;
      } else {
        startPos = 0;
      }
      if (dummy) {
        K(dummy).remove();
      }
    } else if (node.nodeType == 3) {
      testRange.moveStart("character", node.nodeValue.length);
      startPos += node.nodeValue.length;
    }
    if (cmp < 0) {
      startNode = node;
    }
  }
  //<p>abc<img>|</p>
  if (cmp < 0 && startNode.nodeType == 1) {
    return { node: parent, offset: K(parent.lastChild).index() + 1 };
  }
  //<p><table></table><img>ab|c</p>
  if (cmp > 0) {
    while (startNode.nextSibling && startNode.nodeType == 1) {
      startNode = startNode.nextSibling;
    }
  }
  testRange = rng.duplicate();
  _moveToElementText(testRange, parent);
  testRange.setEndPoint("StartToEnd", pointRange);
  startPos -= testRange.text.replace(/\r\n|\n|\r/g, "").length;
  // [textNode1][textNode2]ab|cd
  if (cmp > 0 && startNode.nodeType == 3) {
    var prevNode = startNode.previousSibling;
    while (prevNode && prevNode.nodeType == 3) {
      startPos -= prevNode.nodeValue.length;
      prevNode = prevNode.previousSibling;
    }
  }
  return { node: startNode, offset: startPos };
}
//根据Node和offset，取得表示该位置的原生Range。IE专用
function _getEndRange(node, offset) {
  var doc = node.ownerDocument || node,
    range = doc.body.createTextRange();
  if (doc == node) {
    range.collapse(true);
    return range;
  }
  if (node.nodeType == 1 && node.childNodes.length > 0) {
    var children = node.childNodes,
      isStart,
      child;
    if (offset === 0) {
      child = children[0];
      isStart = true;
    } else {
      child = children[offset - 1];
      isStart = false;
    }
    if (!child) {
      return range;
    }
    if (K(child).name === "head") {
      if (offset === 1) {
        isStart = true;
      }
      if (offset === 2) {
        isStart = false;
      }
      range.collapse(isStart);
      return range;
    }
    if (child.nodeType == 1) {
      var kchild = K(child),
        span;
      if (kchild.isControl()) {
        span = doc.createElement("span");
        if (isStart) {
          kchild.before(span);
        } else {
          kchild.after(span);
        }
        child = span;
      }
      _moveToElementText(range, child);
      range.collapse(isStart);
      if (span) {
        K(span).remove();
      }
      return range;
    }
    node = child;
    offset = isStart ? 0 : child.nodeValue.length;
  }
  var dummy = doc.createElement("span");
  K(node).before(dummy);
  _moveToElementText(range, dummy);
  range.moveStart("character", offset);
  K(dummy).remove();
  return range;
}
// convert native Range to KRange
function _toRange(rng) {
  var doc, range;
  // <table><tr><td></td>|<td></td></tr></table>
  // to <table><tr><td></td><td>|</td></tr></table>
  function tr2td(start) {
    if (K(start.node).name == "tr") {
      start.node = start.node.cells[start.offset];
      start.offset = 0;
    }
  }
  // IE
  if (_IERANGE) {
    if (rng.item) {
      doc = _getDoc(rng.item(0));
      range = new KRange(doc);
      range.selectNode(rng.item(0));
      return range;
    }
    doc = rng.parentElement().ownerDocument;
    var start = _getStartEnd(rng, true),
      end = _getStartEnd(rng, false);
    tr2td(start);
    tr2td(end);
    range = new KRange(doc);
    range.setStart(start.node, start.offset);
    range.setEnd(end.node, end.offset);
    return range;
  }
  // other browser
  var startContainer = rng.startContainer;
  doc = startContainer.ownerDocument || startContainer;
  range = new KRange(doc);
  range.setStart(startContainer, rng.startOffset);
  range.setEnd(rng.endContainer, rng.endOffset);
  return range;
}

// create KRange class
function KRange(doc) {
  this.init(doc);
}
_extend(KRange, {
  init: function(doc) {
    var self = this;
    self.startContainer = doc;
    self.startOffset = 0;
    self.endContainer = doc;
    self.endOffset = 0;
    self.collapsed = true;
    self.doc = doc;
  },
  commonAncestor: function() {
    function getParents(node) {
      var parents = [];
      while (node) {
        parents.push(node);
        node = node.parentNode;
      }
      return parents;
    }
    var parentsA = getParents(this.startContainer),
      parentsB = getParents(this.endContainer),
      i = 0,
      lenA = parentsA.length,
      lenB = parentsB.length,
      parentA,
      parentB;
    while (++i) {
      parentA = parentsA[lenA - i];
      parentB = parentsB[lenB - i];
      if (!parentA || !parentB || parentA !== parentB) {
        break;
      }
    }
    return parentsA[lenA - i + 1];
  },
  setStart: function(node, offset) {
    var self = this,
      doc = self.doc;
    self.startContainer = node;
    self.startOffset = offset;
    if (self.endContainer === doc) {
      self.endContainer = node;
      self.endOffset = offset;
    }
    return _updateCollapsed(this);
  },
  setEnd: function(node, offset) {
    var self = this,
      doc = self.doc;
    self.endContainer = node;
    self.endOffset = offset;
    if (self.startContainer === doc) {
      self.startContainer = node;
      self.startOffset = offset;
    }
    return _updateCollapsed(this);
  },
  setStartBefore: function(node) {
    return this.setStart(node.parentNode || this.doc, K(node).index());
  },
  setStartAfter: function(node) {
    return this.setStart(node.parentNode || this.doc, K(node).index() + 1);
  },
  setEndBefore: function(node) {
    return this.setEnd(node.parentNode || this.doc, K(node).index());
  },
  setEndAfter: function(node) {
    return this.setEnd(node.parentNode || this.doc, K(node).index() + 1);
  },
  selectNode: function(node) {
    return this.setStartBefore(node).setEndAfter(node);
  },
  selectNodeContents: function(node) {
    var knode = K(node);
    if (knode.type == 3 || knode.isSingle()) {
      return this.selectNode(node);
    }
    var children = knode.children();
    if (children.length > 0) {
      return this.setStartBefore(children[0]).setEndAfter(
        children[children.length - 1]
      );
    }
    return this.setStart(node, 0).setEnd(node, 0);
  },
  collapse: function(toStart) {
    if (toStart) {
      return this.setEnd(this.startContainer, this.startOffset);
    }
    return this.setStart(this.endContainer, this.endOffset);
  },
  compareBoundaryPoints: function(how, range) {
    var rangeA = this.get(),
      rangeB = range.get();
    if (_IERANGE) {
      var arr = {};
      arr[_START_TO_START] = "StartToStart";
      arr[_START_TO_END] = "EndToStart";
      arr[_END_TO_END] = "EndToEnd";
      arr[_END_TO_START] = "StartToEnd";
      var cmp = rangeA.compareEndPoints(arr[how], rangeB);
      if (cmp !== 0) {
        return cmp;
      }
      var nodeA, nodeB, nodeC, posA, posB;
      if (how === _START_TO_START || how === _END_TO_START) {
        nodeA = this.startContainer;
        posA = this.startOffset;
      }
      if (how === _START_TO_END || how === _END_TO_END) {
        nodeA = this.endContainer;
        posA = this.endOffset;
      }
      if (how === _START_TO_START || how === _START_TO_END) {
        nodeB = range.startContainer;
        posB = range.startOffset;
      }
      if (how === _END_TO_END || how === _END_TO_START) {
        nodeB = range.endContainer;
        posB = range.endOffset;
      }
      // nodeA和nodeA相同时
      if (nodeA === nodeB) {
        var diff = posA - posB;
        return diff > 0 ? 1 : diff < 0 ? -1 : 0;
      }
      // nodeA是nodeB的祖先时
      nodeC = nodeB;
      while (nodeC && nodeC.parentNode !== nodeA) {
        nodeC = nodeC.parentNode;
      }
      if (nodeC) {
        return K(nodeC).index() >= posA ? -1 : 1;
      }
      // nodeB是nodeA的祖先时
      nodeC = nodeA;
      while (nodeC && nodeC.parentNode !== nodeB) {
        nodeC = nodeC.parentNode;
      }
      if (nodeC) {
        return K(nodeC).index() >= posB ? 1 : -1;
      }
      // nodeB的下一个节点是nodeA的祖先
      nodeC = K(nodeB).next();
      if (nodeC && nodeC.contains(nodeA)) {
        return 1;
      }
      // nodeA的下一个节点是nodeB的祖先
      nodeC = K(nodeA).next();
      if (nodeC && nodeC.contains(nodeB)) {
        return -1;
      }
      //其它情况，暂时不需要
    } else {
      return rangeA.compareBoundaryPoints(how, rangeB);
    }
  },
  cloneRange: function() {
    return new KRange(this.doc)
      .setStart(this.startContainer, this.startOffset)
      .setEnd(this.endContainer, this.endOffset);
  },
  toString: function() {
    //TODO
    var rng = this.get(),
      str = _IERANGE ? rng.text : rng.toString();
    return str.replace(/\r\n|\n|\r/g, "");
  },
  cloneContents: function() {
    return _copyAndDelete(this, true, false);
  },
  deleteContents: function() {
    return _copyAndDelete(this, false, true);
  },
  extractContents: function() {
    return _copyAndDelete(this, true, true);
  },
  insertNode: function(node) {
    var self = this,
      sc = self.startContainer,
      so = self.startOffset,
      ec = self.endContainer,
      eo = self.endOffset,
      firstChild,
      lastChild,
      c,
      nodeCount = 1;
    //node为文档碎片时
    if (node.nodeName.toLowerCase() === "#document-fragment") {
      firstChild = node.firstChild;
      lastChild = node.lastChild;
      nodeCount = node.childNodes.length;
    }
    //startContainer为element时
    if (sc.nodeType == 1) {
      c = sc.childNodes[so];
      if (c) {
        sc.insertBefore(node, c);
        //调整结束节点位置
        if (sc === ec) {
          eo += nodeCount;
        }
      } else {
        sc.appendChild(node);
      }
      //startContainer为text时
    } else if (sc.nodeType == 3) {
      if (so === 0) {
        sc.parentNode.insertBefore(node, sc);
        //调整结束节点位置
        if (sc.parentNode === ec) {
          eo += nodeCount;
        }
      } else if (so >= sc.nodeValue.length) {
        if (sc.nextSibling) {
          sc.parentNode.insertBefore(node, sc.nextSibling);
        } else {
          sc.parentNode.appendChild(node);
        }
      } else {
        if (so > 0) {
          c = sc.splitText(so);
        } else {
          c = sc;
        }
        sc.parentNode.insertBefore(node, c);
        //调整结束节点位置
        if (sc === ec) {
          ec = c;
          eo -= so;
        }
      }
    }
    if (firstChild) {
      self.setStartBefore(firstChild).setEndAfter(lastChild);
    } else {
      self.selectNode(node);
    }
    if (
      self.compareBoundaryPoints(
        _END_TO_END,
        self.cloneRange().setEnd(ec, eo)
      ) >= 1
    ) {
      return self;
    }
    return self.setEnd(ec, eo);
  },
  surroundContents: function(node) {
    node.appendChild(this.extractContents());
    return this.insertNode(node).selectNode(node);
  },
  // 判断range是不是control range
  isControl: function() {
    var self = this,
      sc = self.startContainer,
      so = self.startOffset,
      ec = self.endContainer,
      eo = self.endOffset,
      rng;
    return (
      sc.nodeType == 1 &&
      sc === ec &&
      so + 1 === eo &&
      K(sc.childNodes[so]).isControl()
    );
  },
  // get original range
  get: function(hasControlRange) {
    var self = this,
      doc = self.doc,
      node,
      rng;
    // not IE
    if (!_IERANGE) {
      rng = doc.createRange();
      try {
        rng.setStart(self.startContainer, self.startOffset);
        rng.setEnd(self.endContainer, self.endOffset);
      } catch (e) {}
      return rng;
    }
    // IE control range
    if (hasControlRange && self.isControl()) {
      rng = doc.body.createControlRange();
      rng.addElement(self.startContainer.childNodes[self.startOffset]);
      return rng;
    }
    // IE text range
    var range = self.cloneRange().down();
    rng = doc.body.createTextRange();
    rng.setEndPoint(
      "StartToStart",
      _getEndRange(range.startContainer, range.startOffset)
    );
    rng.setEndPoint(
      "EndToStart",
      _getEndRange(range.endContainer, range.endOffset)
    );
    return rng;
  },
  html: function() {
    return K(this.cloneContents()).outer();
  },
  // 降低range的位置
  // <p><strong><span>123</span>|abc</strong>def</p>
  // postion(strong, 1) -> positon("abc", 0)
  // or
  // <p><strong>abc|<span>123</span></strong>def</p>
  // postion(strong, 1) -> positon("abc", 3)
  down: function() {
    var self = this;
    function downPos(node, pos, isStart) {
      if (node.nodeType != 1) {
        return;
      }
      var children = K(node).children();
      if (children.length === 0) {
        return;
      }
      var left, right, child, offset;
      if (pos > 0) {
        left = children.eq(pos - 1);
      }
      if (pos < children.length) {
        right = children.eq(pos);
      }
      if (left && left.type == 3) {
        child = left[0];
        offset = child.nodeValue.length;
      }
      if (right && right.type == 3) {
        child = right[0];
        offset = 0;
      }
      if (!child) {
        return;
      }
      if (isStart) {
        self.setStart(child, offset);
      } else {
        self.setEnd(child, offset);
      }
    }
    downPos(self.startContainer, self.startOffset, true);
    downPos(self.endContainer, self.endOffset, false);
    return self;
  },
  // 提高range的位置
  // <p><strong><span>123</span>|abc</strong>def</p>
  // positon("abc", 0) -> postion(strong, 1)
  // or
  // <p><strong>abc|<span>123</span></strong>def</p>
  // positon("abc", 3) -> postion(strong, 1)
  up: function() {
    var self = this;
    function upPos(node, pos, isStart) {
      if (node.nodeType != 3) {
        return;
      }
      if (pos === 0) {
        if (isStart) {
          self.setStartBefore(node);
        } else {
          self.setEndBefore(node);
        }
      } else if (pos == node.nodeValue.length) {
        if (isStart) {
          self.setStartAfter(node);
        } else {
          self.setEndAfter(node);
        }
      }
    }
    upPos(self.startContainer, self.startOffset, true);
    upPos(self.endContainer, self.endOffset, false);
    return self;
  },
  // 扩大边界
  // <p><strong><span>[123</span>abc]</strong>def</p> to <p>[<strong><span>123</span>abc</strong>]def</p>
  enlarge: function(toBlock) {
    var self = this;
    self.up();
    function enlargePos(node, pos, isStart) {
      var knode = K(node),
        parent;
      if (
        knode.type == 3 ||
        _NOSPLIT_TAG_MAP[knode.name] ||
        (!toBlock && knode.isBlock())
      ) {
        return;
      }
      if (pos === 0) {
        while (!knode.prev()) {
          parent = knode.parent();
          if (
            !parent ||
            _NOSPLIT_TAG_MAP[parent.name] ||
            (!toBlock && parent.isBlock())
          ) {
            break;
          }
          knode = parent;
        }
        if (isStart) {
          self.setStartBefore(knode[0]);
        } else {
          self.setEndBefore(knode[0]);
        }
      } else if (pos == knode.children().length) {
        while (!knode.next()) {
          parent = knode.parent();
          if (
            !parent ||
            _NOSPLIT_TAG_MAP[parent.name] ||
            (!toBlock && parent.isBlock())
          ) {
            break;
          }
          knode = parent;
        }
        if (isStart) {
          self.setStartAfter(knode[0]);
        } else {
          self.setEndAfter(knode[0]);
        }
      }
    }
    enlargePos(self.startContainer, self.startOffset, true);
    enlargePos(self.endContainer, self.endOffset, false);
    return self;
  },
  // 缩小边界
  // <body>[<p><strong>123</strong></p>]</body> to <body><p><strong>[123]</strong></p></body>
  shrink: function() {
    var self = this,
      child,
      collapsed = self.collapsed;
    while (
      self.startContainer.nodeType == 1 &&
      (child = self.startContainer.childNodes[self.startOffset]) &&
      child.nodeType == 1 &&
      !K(child).isSingle()
    ) {
      self.setStart(child, 0);
    }
    if (collapsed) {
      return self.collapse(collapsed);
    }
    while (
      self.endContainer.nodeType == 1 &&
      self.endOffset > 0 &&
      (child = self.endContainer.childNodes[self.endOffset - 1]) &&
      child.nodeType == 1 &&
      !K(child).isSingle()
    ) {
      self.setEnd(child, child.childNodes.length);
    }
    return self;
  },
  // 创建bookmark，通过插入临时节点标记位置
  createBookmark: function(serialize) {
    var self = this,
      doc = self.doc,
      endNode,
      startNode = K('<span style="display:none;"></span>', doc)[0];
    startNode.id = "__kindeditor_bookmark_start_" + _BOOKMARK_ID++ + "__";
    if (!self.collapsed) {
      endNode = startNode.cloneNode(true);
      endNode.id = "__kindeditor_bookmark_end_" + _BOOKMARK_ID++ + "__";
    }
    if (endNode) {
      self
        .cloneRange()
        .collapse(false)
        .insertNode(endNode)
        .setEndBefore(endNode);
    }
    self.insertNode(startNode).setStartAfter(startNode);
    return {
      start: serialize ? "#" + startNode.id : startNode,
      end: endNode ? (serialize ? "#" + endNode.id : endNode) : null
    };
  },
  // 根据bookmark重新设置range
  moveToBookmark: function(bookmark) {
    var self = this,
      doc = self.doc,
      start = K(bookmark.start, doc),
      end = bookmark.end ? K(bookmark.end, doc) : null;
    if (!start || start.length < 1) {
      return self;
    }
    self.setStartBefore(start[0]);
    start.remove();
    if (end && end.length > 0) {
      self.setEndBefore(end[0]);
      end.remove();
    } else {
      self.collapse(true);
    }
    return self;
  },
  dump: function() {
    console.log("--------------------");
    console.log(
      this.startContainer.nodeType == 3
        ? this.startContainer.nodeValue
        : this.startContainer,
      this.startOffset
    );
    console.log(
      this.endContainer.nodeType == 3
        ? this.endContainer.nodeValue
        : this.endContainer,
      this.endOffset
    );
  }
});

function _range(mixed) {
  if (!mixed.nodeName) {
    return mixed.constructor === KRange ? mixed : _toRange(mixed);
  }
  return new KRange(mixed);
}

K.RangeClass = KRange;
K.range = _range;
K.START_TO_START = _START_TO_START;
K.START_TO_END = _START_TO_END;
K.END_TO_END = _END_TO_END;
K.END_TO_START = _END_TO_START;
